#ifndef KMP_H
#define KMP_H
#include <algorithm>

const char* brute_force_search_first(const char* src, int lenSrc, const char* pat, int lenPat)
{
	int i = 0;
	while (i <= lenSrc - lenPat)
	{
		int j = 0;
		while ( (j < lenPat) && (*(pat + j) == *(src + i + j)) )
		{
			++j;
		}
		if ( j == lenPat)
			return (src+i);
		++i;
	}
	return 0;
}

char* brute_force2_search_first( char* src, int lenSrc, const char* pat, int lenPat)
{
	int i = 0;
	//while ( i < 
	return 0;
}

void computer_border(char* pat, int patLen, int* mp_shift)
{
	int* border = new int[patLen];
	memset(border, 0, sizeof(int) * patLen);
	border[0] = -1; 
	int t = -1;
	for (int i = 1; i < patLen; ++i)
	{
		while ( (t >= 0) && (pat[t+1] != pat[i]) )
		{
			t = border[t];
		}
		++t;
		border[i] = t;
	}
	for (int i = 0; i < patLen; ++i)
	{
		mp_shift[i] = i - border[i];
	}
}

char* mp_search( char* src, int srcLen, char* pat, int patLen)
{
	int* mp_shift = new int[patLen];
	memset(mp_shift, 0, sizeof(int) * patLen);
	computer_border(pat, patLen, mp_shift);
	int i = 0;
	int j = 0;
	while ( i <= srcLen - patLen )
	{
		while ( (j < patLen) && (*(pat + j)  == *(src + i + j)) )
		{
			++j;
		}
		if ( j == patLen )
		{
			delete[] mp_shift;
			return ( src + i );
		}
		i += mp_shift[j];
		j = std::max(0, j - mp_shift[j]);
	}
	delete[] mp_shift;
	return 0;
}

char* kmp( char* src, const char* pat)
{
	return 0;
}


#endif